1. Field of the Invention
The present invention relates to error-correction (EC) coding and, more specifically, to concatenated error coding and decoding.
2. Description of the Related Art
In digital communication systems, information is communicated from a transmitter to a receiver over a channel that is typically impaired by some amount of noise. Similarly, in digital storage systems (e.g., magnetic, optical, semiconductor, and organic storage systems) impairments to the information can be introduced during transmission to the storage medium, storage on the storage medium, and read-back from the storage medium. The rate at which errors occur, referred to as the bit-error rate (BER), is a very important design criterion for digital communication links and for data storage. The BER is usually defined to be the ratio of the number of bit errors introduced to the total number of bits. Usually the BER must be kept lower than a specified value, which depends on the application. In both communications and storage systems, EC-coding techniques based on the addition of redundancy to the original messages are commonly employed to ensure that the original information is recovered as accurately as possible in the presence of impairments such as noise and inter-symbol interference (ISI). An introduction and overview of EC codes can be found in Bernard Skalar and Fredric J. Harris, “The ABCs of linear block codes,” IEEE Signal Processing Magazine, Jul 2004, pp. 14-35, incorporated herein by reference in its entirety.
Generally, EC decoders fall into two major classes: algebraic hard decoders and iterative soft decoders. Hard decoding refers to a process whereby received signals or signal samples read back from a storage medium are decoded directly to digital symbols (e.g., blocks of binary data), whereas soft decoding refers to a process that results in more probabilistic information, such as the probability that a particular sample is a binary zero or a binary one. For example, a typical soft output decoder might use a 4-bit signed binary value to represent each received sample. A value close to +7 is considered to have a high probability of representing a received binary one, whereas a value that is close to −8 is considered to have a high probability of representing a received binary zero. Iterative decoding can improve the decoding accuracy by generating more-reliable bit estimates from previous, less-reliable bit estimates.
Iterative decoders (e.g., turbo decoders, low-density parity-check (LDPC) decoders, and iterative array decoders) have the attractive characteristic of high coding gain. Coding gain is defined as the increase in efficiency that a coded signal provides over an unencoded signal. Expressed in decibels, the coding gain can indicate, for example, a level of transmit power reduction that can be achieved to maintain the same data rate through a channel when a particular code is employed relative to no code. One characteristic of iterative decoders is that there is no closed-form expression for the coding gain of the decoder. An expression is said to be a closed-form expression if it can be expressed analytically in terms of a bounded number of operations. For example, an infinite sum would generally not be considered closed-form. Since there is no closed-form expression for the coding gain of an iterative decoder, the coding gain of these decoders is typically determined by simulation. Unfortunately, when the target BER of an iterative decoder is very low (e.g., 10−15 or lower), simulation of the decoder is impractical using today's computing systems. So, for example, a particular iterative decoder might be able to be shown by simulation to exhibit significant coding gain for a system whose target BER is 10−5 but its performance cannot be determined for a target BER of 10−15. Further, empirical data tends to indicate that, for iterative decoders, performance tends to flatten out at a low BER, raising further concern that iterative decoders may fail to correct all errors in a reasonable number of iterations. More information on array codes and LDPC codes can be found in J. L. Fan, “Array codes as Low-Density Parity Check codes,” Proc. 38th Allerton Conference on Communication, Control, and Computing, 955-956, Sep. 2000, incorporated herein by reference in its entirety. More information on turbo codes can be found in B. Skiar, “A Primer on Turbo Code Concepts,” pp. 94-102, IEEE Communications Magazine, December 1997, incorporated herein by reference in its entirety.
Algebraic decoders (e.g., Hamming decoders, Reed-Solomon decoders, Bose-Chaudhuri-Hocquenghem (BCH) decoders, and algebraic array decoders), on the other hand, can be less efficient (e.g., lower coding gain) than iterative decoders; however, the performance of algebraic decoders can be calculated analytically at an arbitrarily low target BER. Thus, given a particular target BER, and given an anticipated channel error rate, a closed-form expression can be used to determine whether a particular algebraic code can be used to meet the target BER or not.
For data storage applications, the corrected bit-error rate (i.e., the BER after error correction) is preferably on the order of 10−15 or smaller. Bit errors can be introduced in data storage applications, for example, because of mistracking of read heads, the fly-height variation of a read head relative to the recording medium, the bit density, and the signal-to-noise ratio (SNR) of the system. Today, the goal of data storage applications is to realize storage densities of one tera-bit per square inch (1 Tbit/in2) and higher. Such a high bit density generates high intersymbol interference (ISI), which complicates the task of realizing low BERs. Further, with such high bit densities, the physical space each bit takes up on the recording medium becomes relatively small, resulting in relatively low signal strength, which affects the SNR. In addition, computationally complex encoding/decoding schemes make the associated decoding operation difficult to implement at high bit rates.
Accordingly, there exists a need for a coding scheme that leads to corrected BERs of 10−15 or lower despite the complications of large ISI and low SNR that are typically associated high bit densities, such as 1 Tbit/in2. Further, there exists a need for such a coding scheme to permit encoding/decoding at high data rates.